package hwTwo2;

import javax.swing.*;
import java.awt.*;
import java.util.Arrays;
import java.util.stream.IntStream;

public class MergeSortAnalysis {

    // 自顶向下归并排序
    static class TopDownMergeSort {
        private int accessCount = 0;

        public int countAccess(int[] arr) {
            accessCount = 0;
            int[] aux = Arrays.copyOf(arr, arr.length);
            sort(arr, aux, 0, arr.length - 1);
            return accessCount;
        }

        private void sort(int[] arr, int[] aux, int lo, int hi) {
            if (hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            sort(arr, aux, lo, mid);
            sort(arr, aux, mid + 1, hi);
            merge(arr, aux, lo, mid, hi);
        }

        private void merge(int[] arr, int[] aux, int lo, int mid, int hi) {
            for (int k = lo; k <= hi; k++) {
                aux[k] = arr[k];
                accessCount += 2; // 读和写
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                if (i > mid) {
                    arr[k] = aux[j++];
                    accessCount += 2;
                } else if (j > hi) {
                    arr[k] = aux[i++];
                    accessCount += 2;
                } else if (aux[j] < aux[i]) {
                    arr[k] = aux[j++];
                    accessCount += 4; // 比较 + 读写
                } else {
                    arr[k] = aux[i++];
                    accessCount += 4;
                }
            }
        }
    }

    // 自底向上归并排序
    static class BottomUpMergeSort {
        private int accessCount = 0;

        public int countAccess(int[] arr) {
            accessCount = 0;
            int n = arr.length;
            int[] aux = Arrays.copyOf(arr, n);
            for (int sz = 1; sz < n; sz = sz + sz) {
                for (int lo = 0; lo < n - sz; lo += sz + sz) {
                    merge(arr, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
                }
            }
            return accessCount;
        }

        private void merge(int[] arr, int[] aux, int lo, int mid, int hi) {
            for (int k = lo; k <= hi; k++) {
                aux[k] = arr[k];
                accessCount += 2; // 读和写
            }

            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                if (i > mid) {
                    arr[k] = aux[j++];
                    accessCount += 2;
                } else if (j > hi) {
                    arr[k] = aux[i++];
                    accessCount += 2;
                } else if (aux[j] < aux[i]) {
                    arr[k] = aux[j++];
                    accessCount += 4; // 比较 + 读写
                } else {
                    arr[k] = aux[i++];
                    accessCount += 4;
                }
            }
        }
    }

    // 绘制曲线图
    public static class PlotGraph extends JPanel {
        private final int[] N_values;
        private final int[] topDownCounts;
        private final int[] bottomUpCounts;
        private final double[] upperBounds;

        public PlotGraph(int[] N_values, int[] topDownCounts, int[] bottomUpCounts, double[] upperBounds) {
            this.N_values = N_values;
            this.topDownCounts = topDownCounts;
            this.bottomUpCounts = bottomUpCounts;
            this.upperBounds = upperBounds;
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);
            Graphics2D g2 = (Graphics2D) g;
            g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

            int width = getWidth();
            int height = getHeight();

            int margin = 50;
            int graphWidth = width - 2 * margin;
            int graphHeight = height - 2 * margin;

            // Find max value
            int maxCount = IntStream.concat(Arrays.stream(topDownCounts), Arrays.stream(bottomUpCounts)).max().orElse(1);
            double maxBound = Arrays.stream(upperBounds).max().orElse(1);

            // X and Y axis
            g2.drawLine(margin, height - margin, margin, margin); // Y-axis
            g2.drawLine(margin, height - margin, width - margin, height - margin); // X-axis

            // Draw labels
            g2.drawString("0", margin - 15, height - margin + 15);
            g2.drawString("N", width - margin, height - margin + 15);
            g2.drawString("Access Count", margin - 40, margin - 10);

            // Scale
            double xScale = (double) graphWidth / (N_values.length - 1);
            double yScale = (double) graphHeight / Math.max(maxCount, maxBound);

            // Draw data
            drawCurve(g2, N_values, topDownCounts, xScale, yScale, margin, height, Color.BLUE, "Top-Down");
            drawCurve(g2, N_values, bottomUpCounts, xScale, yScale, margin, height, Color.GREEN, "Bottom-Up");
            drawCurve(g2, N_values, upperBounds, xScale, yScale, margin, height, Color.RED, "6NlgN");
        }

        private void drawCurve(Graphics2D g2, int[] xValues, int[] yValues, double xScale, double yScale, int margin, int height, Color color, String label) {
            g2.setColor(color);
            for (int i = 0; i < xValues.length - 1; i++) {
                int x1 = margin + (int) (i * xScale);
                int y1 = height - margin - (int) (yValues[i] * yScale);
                int x2 = margin + (int) ((i + 1) * xScale);
                int y2 = height - margin - (int) (yValues[i + 1] * yScale);
                g2.drawLine(x1, y1, x2, y2);
            }
        }

        private void drawCurve(Graphics2D g2, int[] xValues, double[] yValues, double xScale, double yScale, int margin, int height, Color color, String label) {
            g2.setColor(color);
            for (int i = 0; i < xValues.length - 1; i++) {
                int x1 = margin + (int) (i * xScale);
                int y1 = height - margin - (int) (yValues[i] * yScale);
                int x2 = margin + (int) ((i + 1) * xScale);
                int y2 = height - margin - (int) (yValues[i + 1] * yScale);
                g2.drawLine(x1, y1, x2, y2);
            }
        }
    }

    public static void main(String[] args) {
        int[] N_values = IntStream.rangeClosed(1, 512).toArray();
        int[] topDownCounts = new int[N_values.length];
        int[] bottomUpCounts = new int[N_values.length];
        double[] upperBounds = new double[N_values.length];

        TopDownMergeSort topDownSorter = new TopDownMergeSort();
        BottomUpMergeSort bottomUpSorter = new BottomUpMergeSort();

        for (int i = 0; i < N_values.length; i++) {
            int N = N_values[i];
            int[] arr = IntStream.rangeClosed(1, N).map(x -> N - x).toArray(); // 最坏情况：逆序数组
            topDownCounts[i] = topDownSorter.countAccess(Arrays.copyOf(arr, arr.length));
            bottomUpCounts[i] = bottomUpSorter.countAccess(Arrays.copyOf(arr, arr.length));
            upperBounds[i] = N > 1 ? 6 * N * Math.log(N) / Math.log(2) : 0; // 6NlgN
        }

        // 绘制图形
        JFrame frame = new JFrame("Merge Sort Array Access Counts");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(800, 600);
        frame.add(new PlotGraph(N_values, topDownCounts, bottomUpCounts, upperBounds));
        frame.setVisible(true);
    }
}